package likou;

import java.util.HashSet;
import java.util.Set;

/**
 * @Info:
 * @Author: Tangxz
 * @Date: 2020/09/15 21:17
 */
public class _1044 {
    public String longestDupSubstring(String S) {
        String daan = "";
        if(S.length()<2){
            return daan;
        }
        //i是长度
        for(int i = S.length()-1 ; i>0 ; i-- ){
            String now = search(S,i);
            daan = daan.length()>now.length()?daan:now;
            if(!daan.isEmpty()){
                return daan;
            }
        }
        return daan;
    }
    //5,4
    public String search(String S, int length){
        Set<String> set = new HashSet<>();
        String testStr = S.substring(0,length);
        set.add(testStr);
        System.out.println(testStr);
        for(int i=1;i<=S.length()-length;i++){
            String now = S.substring(i,length+i);
            if(set.contains(now)){
                return now;
            }else{
                set.add(now);
            }
        }
        return "";
    }
}
